The present invention relates to content addressable memory (CAM) devices, and particularly to CAM based systems that can include multiple CAM devices.
Content addressable memory (CAM) systems typically include one or more CAM devices. A CAM device can include circuitry for performing one or more types of search operations. In a search operation, a comparand (or key) may be compared to multiple entries to see if all or a portion of the key matches an entry. After a search operation, a CAM device may give a search result as an output. Typically a search result may include an xe2x80x9cindexxe2x80x9d value which may be used to access associated data or to provide data itself.
CAM devices may take a variety of forms. As but a few of the possible examples, some CAM devices are based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processes.
To better understand the various features and aspects of CAM systems, and CAM system performance, two conventional CAM systems will now be described.
A first conventional CAM system is shown in FIG. 16 and designated by the general reference character 1600. A conventional CAM system 1600 may include one or more CAM devices, each of which may perform a search operation. In the example of FIG. 16, a CAM system 1600 includes xe2x80x9cn+1xe2x80x9d CAM devices, shown as 1602-0 to 1602-n. A CAM system 1600 may perform search operations in response to commands from a requesting device. In FIG. 16, a requesting device is a network processing unit (NPU) 1604.
FIG. 16 shows an example of a bus based CAM system. In a bus based CAM system, CAM devices may be commonly connected to a requesting device and to one another by a common bus. Thus, in FIG. 16 CAM devices (1602-0 to 1602-n) can be commonly connected to each other and to an NPU 1604 by a bus 1606.
A drawback to bus based systems can be speed limitations. Larger interconnect lengths of bus lines as well as the input capacitances of each device can present considerable capactive loads for an NPU 1604 and CAM devices (1602-0 to 1602-n). Thus, while a bus based CAM system 1600 may be scaled up by increasing the number of CAM devices (1602-0 to 1602-n), such an approach may increase bus loading, reducing performance.
A bus based CAM system 1600 may have other drawbacks. Some sort of bus arbitration may be necessary to select one of multiple possible results. That is, while a search request may be issued from an NPU 1604 to CAM devices (1602-0 to 1602-n) simultaneously, individual search results for the CAM devices (1602-0 to 1602-n) can be generated, and some sort of mechanism may have to be included to select which particular response would be received separately by an NPU 1604. Special bus arbitration hardware may allow a xe2x80x9cwinningxe2x80x9d device to transmit a result to an NPU 1604. Such bus arbitration hardware may be undesirably complex in the event a system includes software assigned priority between CAM devices (1602-0 to 1602-n).
Further, some additional processing is needed to process multiple results from multiple CAM devices. As but one example, more than one CAM device (1602-0 to 1602-n) may generate a match result in response to a key. Some sort of evaluation would then be necessary to establish a precedence between CAM devices (1602-0 to 1602-n). It is noted that such a precedence may make a system inflexible. As more and more CAM devices (1602-0 to 1602-n) are added, evaluating a search result can require that precedence between all devices must be known to ensure a highest precedence device result is provided as an output.
A second conventional CAM system is set forth in FIG. 17 and designated by the general reference character 1700. A second conventional CAM system 1700 may include a number of CAM devices (1702-0 to 1702-3) having common connections to a command and data bus 1704, as well as separate common connections to an index or result bus 1706. Optionally, an index or result bus 1706 may be connected to one or more memory devices 1708, such as a static random access memory (SRAM).
In a system like that shown in FIG. 17, a search command may be issued from a host device 1710 on a command and data bus 1704. CAM devices (1702-0 to 1702-3) may process such commands and generate results, which may be output on an index or result bus 1706. Results may be returned to a command issuing host device 1710 by way of a result bus. Optionally, results may be applied to one or more memory devices 1708 to generate data that may then be accessed by a host device 1710.
A second conventional system 1700 may suffer from many of the drawbacks noted above. If a number of CAM devices is increased, bus loading can grow correspondingly. Further, some sort of logical protocol may be necessary to establish priority between results of multiple CAMs. As the number of CAM devices grows, such a protocol may get more complex or involve greater time periods for execution.
In light of the above, it would be desirable to arrive at a CAM system that does not rely on a common bus between a request issuing device and multiple CAM devices, but at the same time can provide improved performance over conventional cascaded approaches.
It would also be desirable to arrive at some way of addressing the drawback of having to process multiple CAM device results in a CAM system.
It would also be desirable to arrive at a CAM device that may be cascaded with other like CAM devices, and yet not suffer from the various drawbacks of conventional CAM systems.
According to the present invention, a content addressable memory (CAM) system may include a plurality of CAM devices arranged in series. A CAM system may include at least one input port that receives requests to perform particular operations. A CAM system may also include at least one output port that may provide a response based on responses generated by each CAM device.
According to one aspect of the embodiments, each CAM device may include a request path for transferring a request received at an input port to one or more output ports. Thus, requests may flow through sequential CAM devices, and not on a common bus.
According to another aspect of the embodiments, each CAM device can vote between multiple responses. In particular, each CAM device may include a first vote portion. A first vote portion may generate an output response based on a xe2x80x9clocalxe2x80x9d response generated by the CAM device and a xe2x80x9cremotexe2x80x9d response generated by some other CAM device at a previous location in the series.
According to another aspect of the embodiments, further voting capabilities may be provided by a second vote portion in each CAM device. A second vote portion may generate a response based on two or more remote responses, each generated by different CAM devices at previous locations in the series.
According to another aspect of the embodiments, one response may be based on multiple responses according to precedence data associated with each response. Such precedence data may take a variety of forms. In one arrangement, precedence data may include a status value and a chip value. A status value may be assigned to a particular response type or according to a programmed priority value. A chip value may be a unique value assigned to a CAM device generating a response. Selection of response may be accomplished with a magnitude comparator circuit that compares status and chip values of responses.
According to another aspect of the embodiments, CAM devices in the system may be arranged into two or more branches. Thus, requests may be supplied to multiple branches by xe2x80x9cbranchingxe2x80x9d CAM devices. Similarly, responses from multiple branches may be merged by merging CAM devices. A branching CAM device can receive at least one request at an input port and provide such a request at two or more output ports. Each output port may be connected to a different branch of CAM devices. A merging CAM device can receive remote responses on different input ports, where each remote response may be generated from a different branch of CAM devices. A merging CAM device may generate a response based on such remote responses.
According to another aspect of the embodiments, each CAM device may generate a response from a request with a same latency.
According to the present invention, a CAM device may have a unique structure to enable cascading of multiple CAM devices. According to particular embodiments, a CAM device may include a search portion that generates a response from a received operation request. In addition, a CAM device can include a first vote portion. A first vote portion may generate a response based on a local response generated by a search portion and one or more remote response received at input ports.
According to one aspect of the embodiments, a CAM device vote portion may include a vote circuit. A vote circuit may perform an operation that generates an output response based on different responses, such as local and remote responses. In one embodiment, a vote circuit may include a magnitude comparator that compares portions of responses.
According to another aspect of the embodiments, a CAM device may include both a first and second vote portion. A second vote portion may generate a response based on two remote responses received at different input ports.
According to another aspect of the embodiments, a CAM device can include an interface portion that can provide additional connections to a CAM device. An interface portion may include a multiplexer that selects between an input port and a secondary port. An interface portion may also include an interface circuit that transfers data between one clock domain and another. As but one example, an interface circuit may transfer data between separate input and output paths and a bidirectional bus.
According to the present invention, a method of operating a CAM system may include applying a request to a plurality of CAM devices arranged in series. The request may flow in one direction through CAM devices. Responses generated by CAM devices from a request may flow in the same one direction.
According to one aspect of the embodiments, in a CAM system operating method, requests may flow through each CAM device from an input port to an output port.
According to another aspect of the embodiments, in a CAM system operating method, responses may flow from one CAM device to the next. In particular, for CAM devices that are preceded by other CAM devices in the series, a CAM device may generate a response based on a local response generated from the CAM device and a remote response generated from a preceding CAM device in the series.
According to another aspect of the embodiments, in a CAM system operating method, requests may be branched to flow down two or more CAM device branches. A branching CAM can receive a request and provide such a request on two or more output ports.
According to another aspect of the embodiments, in a CAM system operating method, responses from two or more CAM device branches may be merged. A merging CAM can receive responses on two or more input ports, and generate a merged response based on such received responses.